import java.util.ArrayDeque;
import java.util.Deque;

public class Sort {

    /**
     *  快速排序
     *  时间复杂度：
     *       最坏情况：当数据给定的是1 2 3 4 5 6 7.....有序的情况下 确实是O(n^2)
     *                          9 8 7 6 5 4
     *       最好情况：O(N*logN)
     *  空间复杂度：
     *      最坏情况：O(N)
     *      最好情况：O(logN)
     * 稳定性：
     *      不稳定性
     * @param array
     */
    public static void quickSort(int[] array) {
        quickNor(array,0,array.length - 1);
    }

    //优化 —— 三数取中法 —— 可以使递归的次数减少
    //将 left下标、 right下标 和两个下标的中间下标mid
    //返回 left、right和 mid 下标，对应的值位于中间的下标
    public static int getMiddleNum(int[] array,int left,int right) {
        int mid = (left + right)/2;
        if(array[left] > array[right]) {
            if(array[mid] < array[right]) {
                return right;
            } else if (mid > array[left]) {
                return left;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[left]) {
                return left;
            } else if (mid > array[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }

    public static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        //因为越递归越有序，所以递归到一定程度可以使用 直接插入排序
        //如果 有 6 个元素，直接使用直接插入排序，并返回
        if(end - start + 1 < 7) {
            insertSortRange(array,start,end);
            return;
        }
        //三数取中法
        int midIndex = getMiddleNum(array,start,end);
        swap(array,start,midIndex);

        int pivot = partition2(array,start,end);
        quick(array,start,pivot - 1);
        quick(array,pivot + 1,end);
    }

    //范围的直接插入排序
    private static void insertSortRange(int[] array, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= start; j--) {
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //挖坑法——常用的方法
    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    //Hoare法——比较常见
    public static int partitionHoare(int[] array, int left, int right) {
        int tmp = array[left];
        //记录基准的下标，防止调整后找不到
        int tmpLeft = left;
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            while(left < right && array[left] <= tmp) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, tmpLeft, right);
        return left;
    }

    //双指针法——了解
    public static int partition2(int[] array, int left, int right) {
        int prev = left;
        int cur = left + 1;
        while (cur <= right) {
            //这个 if 语句意思是
            //如果 cur 下标的值小于基准值时 prev 和 cur 一起前进
            //如果 cur 下标的值大于基准值时 prev 不走 cur 前进，prev 留在大的数之前
            //cur 再遇见小于基准值的，将 prev++，在交换 prev 和 cur 的值
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,prev,cur);
            }
            cur++;
        }
        swap(array,left,prev);
        return prev;
    }



    //非递归的快速排序方法 —— 使用栈
    public static void quickNor(int[] array,int start,int end) {
        Deque<Integer> stack = new ArrayDeque<>();
        int piovt = partition(array, start, end);

        //将 start、piovt - 1、piovt + 1 和 end压入栈中

        if(piovt > start + 1){
            stack.push(start);
            stack.push(piovt - 1);
        }
        if(piovt < end - 1) {
            stack.push(piovt + 1);
            stack.push(end);
        }
        //while 循环 直到 栈 stack为空
        while(!stack.isEmpty()) {
            //弹出 后两个用 end 和 start 接收，先用end接收因为最后 压入的元素是后面的
            end = stack.pop();
            start = stack.pop();

            piovt = partition(array, start, end);
            //在压入新的范围的start、piovt - 1、piovt + 1 和 end
            //反复执行，直到栈为空，顺序就排好了
            if(piovt > start + 1){
                stack.push(start);
                stack.push(piovt - 1);
            }
            if(piovt < end - 1) {
                stack.push(piovt + 1);
                stack.push(end);
            }
        }
    }
}
